package com.df.sort;

import java.util.Arrays;

/**
 * 快排
 *
 * @author dongfang
 */
public class Quick {
    /**
     * 快速排序
     * <pre>
     * 将任务进行分割，然后各个击破
     * 在某种特定的情况下，是最快的算法
     * 基本原理：
     *      1.设定一个基准值（也就是轴）
     *      2.将比轴小的值，移到轴的左边，形成左子数列
     *      3.将比轴大的值，移到轴的右边，形成右子数列
     *      4.分别对左子数列和右子数列做上述三个步骤(递归)，直到左子数列或右子数列只剩一个值或没有数值
     * 快速排序的效率：选择的基准值越接近数列平均值越好
     * 基准值（轴）的选择方式：
     *      - 固定位置：第一位，或者最后一位
     *      - 随机选择一位
     *      - 随机取三个值，然后取中间值
     * 不稳定算法
     *
     * </pre>
     *
     * @param array
     */
    public static void quick(int[] array) {
        int num = quickPartition(array, 0, array.length - 1);
        System.out.println("quick num [" + num + "]");

    }

    /**
     * 快速排序分治方法 , 理论是对的，但是实现是错的，哈哈哈哈
     * <pre>
     * 1.以array[l]为轴，作为基准值进行分治
     * 2.将比轴小的值，移到轴的左边，形成左子数列
     * 3.将比轴大的值，移到轴的右边，形成右子数列
     * 4.分别对左子数列和右子数列做上述三个步骤(递归)，直到左子数列或右子数列只剩一个值或没有数值
     * </pre>
     * 每次一次分治，都会把轴的值给排序好
     *
     * @param array
     * @param l     起始位置
     * @param r     结束位置
     */
    private static int quickPartition(int array[], int l, int r) {
        int num = 0;

        if (l < r) {
            int i = l, j = r, temp = array[l];
            while (i < j) {
                while (i < j && array[j] >= temp) // 从右向左找第一个小于x的数
                {
                    System.out.println("[" + num + "][" + temp + "][" + i + "][" + j + "] : " + Arrays.toString(array));
                    j--;
                }
                if (i < j) {
                    array[i] = array[j];
                    System.out.println("[" + num + "][" + temp + "][" + i + "][" + j + "] : " + Arrays.toString(array));
                    num++;
                    i++;
                }
                while (i < j && array[i] < temp) // 从左向右找第一个大于等于x的数
                {
                    System.out.println("[" + num + "][" + temp + "][" + i + "][" + j + "] : " + Arrays.toString(array));
                    i++;

                }
                if (i < j) {
                    array[j] = array[i];
                    System.out.println("[" + num + "][" + temp + "][" + i + "][" + j + "] : " + Arrays.toString(array));
                    num++;
                    j--;
                }
            }
            array[i] = temp;
            //print(array);
            System.out.println("[" + num + "][" + temp + "][" + i + "][" + j + "] : " + Arrays.toString(array));
            num++;
            num += quickPartition(array, l, i - 1); // 递归调用
            num += quickPartition(array, i + 1, r);
        }

        return num;
    }

    public static void main(String[] args) {
        q(new int[]{6, 1, 2, 7, 9, 3, 4, 5, 10, 8});
        quick(new int[]{6, 1, 2, 7, 9, 3, 4, 5, 10, 8});
    }

    static void print(int[] array) {
        for (int i : array) {
            System.out.print(i);
            System.out.print(",");

        }
        System.out.println("");
    }

    public static void q(int[] a) {

        int num = qp(a, 0, a.length - 1);
        System.out.println("quick num [" + num + "]");
    }

    public static int qp(int[] array, int l, int r) {
        int num = 0;
        if (l >= r) {
            return num;
        }
        System.out.println("1->[" + l + "][" + r + "] : " + Arrays.toString(array));


        int t = array[l];
        int i = l;
        int j = r;

        while (i < j) {
            while (i < j && array[j] >= t) {
                j--;
                System.out.println("j->[" + i + "][" + j + "] : " + Arrays.toString(array));

            }
            while (i < j && t >= array[i]) {
                i++;
                System.out.println("i->[" + i + "][" + j + "] : " + Arrays.toString(array));

            }

            if (i < j) {
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
                System.out.println("2->[" + i + "][" + j + "] : " + Arrays.toString(array));
                num++;

            }
        }
//
        array[l] = array[i];
        array[i] = t;
        num++;
//
        System.out.println("3->[" + i + "][" + j + "] : " + Arrays.toString(array));

        num += qp(array, l, i - 1);
        num += qp(array, i + 1, r);
        return num;
    }


}
